package com.xy.data.structure.redblacktree;

/**
 * @author x
 */
public class RedBlackTree {

    private final int R = 0;
    private final int B = 1;

    private Node root = null;

    class Node {
        int data;
        int color = R;
        Node left;
        Node right;
        Node parent;

        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 插入部分
     */
    public void insert(Node root, int data) {
        if (root.data < data) {
            if (root.right == null) {
                root.right = new Node(data);
            } else {
                insert(root.right, data);
            }
        } else {
            if (root.left == null) {
                root.left = new Node(data);
            } else {
                insert(root.left, data);
            }
        }
    }

    public void leftRotate(Node node) {
        //如果该节点的父节点为空
        if (node.parent == null) {
            Node E = root;
            Node S = E.right;

            //移S的左子树
            E.right = S.left;
            S.left = E;
            //修改E的指针
            E.parent = S;
            //修改S的指针
            S.parent = null;
        } else {
            Node E = node;
            Node S = E.right;

            E.right = S.left;
            S.left = E;

            S.parent = E.parent;
            E.parent = S;
        }
        //

    }

    public void rightRotate(Node node) {
        if (node.parent == null) {
            Node S = root;
            Node E = S.left;

            S.left = E.right;
            E.right = S;

            S.parent = E;
            E.parent = null;
        }
    }
}
